package LeetCodeTest.PrimaryAlgorithmTest.LinkList;

public class ReverseList {
    /**
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 示例 1：
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     * 示例 2：
     * 输入：head = [1,2]
     * 输出：[2,1]
     * 示例 3：
     * 输入：head = []
     * 输出：[]
     * 提示：
     * 链表中节点的数目范围是 [0, 5000]
     * -5000 <= Node.val <= 5000
     *
     * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnhm6/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public static void main(String[] args) {
        ListNode head5 = new ListNode(5);
        ListNode head4 = new ListNode(4,head5);
        ListNode head3 = new ListNode(3,head4);
        ListNode head2 = new ListNode(2,head3);
        ListNode head1 = new ListNode(1,head2);
        ListNode head0 = new ListNode(0,head1);
        System.out.println(head0.val);
        System.out.println(head1.val);
        System.out.println(head2.val);
        System.out.println(head3.val);
        System.out.println(head4.val);
        System.out.println(head5.val);
        System.out.println("---------------------------------------------");
        ListNode listNode = new ReverseList().reverseList(head0);
        System.out.println(listNode.val);
        System.out.println(listNode.next.val);
        System.out.println(listNode.next.next.val);
        System.out.println(listNode.next.next.next.val);
        System.out.println(listNode.next.next.next.next.val);
        System.out.println(listNode.next.next.next.next.next.val);
    }

    /**
     * 思路1：利用栈的特性
     * 思路2：利用递归方法
     * @param head 第一个标签
     * @return 结果链表
     */
    public ListNode reverseList(ListNode head) {
        return recurrenceReverseList(head, null);
    }

    public ListNode recurrenceReverseList(ListNode head,ListNode newHead){
        if (head == null){
            return newHead;
        }
        ListNode next = head.next;
        head.next = newHead;
        return recurrenceReverseList(next,head);
    }
}
